<?php
/**
 * 基于固定数组实现的循环队列
 * 循环队列规则：
 * head == tail 队列空
 * (tail + 1) % capacity == head 队列满(实际申请空间的时候 多申请一个)
 * 出队，头指针移动(head + 1) % capacity
 * 入队，尾指针移动(tail + 1) % capacity
 */

namespace Xxb\XxbPhpAlgo;

use Xxb\XxbPhpAlgo\Contract\XxbQueueInterface;

class ArrayLoopQueue implements XxbQueueInterface
{
    private $data;

    /**
     * 队头指针
     * @var int
     */
    private $bottom;

    /**
     * 队尾指针
     * @var int
     */
    private $top;

    private $size;

    public function __construct($capacity = 10)
    {
        if ($capacity <= 0) {
            throw new \InvalidArgumentException('illegal capacity, it must be positive integer!');
        }
        $this->data = new \SplFixedArray($capacity + 1);
        $this->size = $this->bottom = $this->top = 0;
    }

    /**
     * 调整数组容量
     * @param $capacity
     */
    public function resize($capacity)
    {
        if ($capacity <= 0) {
            throw new \InvalidArgumentException('illegal capacity, it must be positive integer!');
        }
        $newData = new \SplFixedArray($capacity + 1);
        for ($i=$this->bottom, $j=0; $i!=$this->top; $i=($i+1) % $this->data->getSize(),$j++) {
            $newData[$j] = $this->data[$i];
        }
        $this->data = $newData;
        $this->bottom = 0;
        $this->top = $j;
    }

    public function push($value)
    {
        if (($this->top + 1) % $this->data->getSize() == $this->bottom) {
            // 队列满了，进行2倍扩容
            $this->resize($this->data->getSize() * 2);
        }
        $this->data[$this->top] = $value;
        $this->top = ($this->top + 1) % $this->data->getSize();
        $this->size++;
    }

    public function shift()
    {
        if ($this->isEmpty()) {
            throw new \RuntimeException('queue is empty!');
        }
        $this->data[$this->bottom] = null;
        $this->bottom = ($this->bottom + 1) % $this->data->getSize();
        $this->size--;
        $capacity = ceil($this->data->getSize() / 4);
        if ($capacity > 0 && $capacity == $this->size) {
            // 队列成员个数少到容量的四分之一，进行缩容
            $this->resize($capacity);
        }
    }

    public function top()
    {
        if ($this->isEmpty()) {
            throw new \RuntimeException('queue is empty!');
        }
        return $this->data[$this->top];
    }

    public function bottom()
    {
        if ($this->isEmpty()) {
            throw new \RuntimeException('queue is empty!');
        }
        return $this->data[$this->bottom];
    }

    public function isEmpty()
    {
        return $this->bottom == $this->top;
    }

    public function getSize()
    {
        return $this->size;
    }

    public function __toString()
    {
        $str = 'queue: 队头 [';
        for ($i=$this->bottom; $i!=$this->top; $i=($i + 1) % $this->data->getSize()) {
            $str .= $this->data[$i] . ',';
        }
        $str = rtrim($str, ',');
        return $str . ']';
    }

    public function getCapacity()
    {
        return $this->data->getSize();
    }
}
